#include "main/utils.h"
using namespace std;

void sumInSortedVec(const vector<int> &vec, vector<vector<int>> &ret, const int &i) {
  int begin = i + 1;
  int end = vec.size() - 1;
  while (begin < end) {
    int cur_sum = vec[i] + vec[begin] + vec[end];
    if (cur_sum == 0) {
      ret.push_back({vec[i], vec[begin], vec[end]});
      int tmp = vec[begin];
      while (begin < end && vec[begin] == tmp) {
        ++begin;
      }
    } else if (cur_sum < 0) {
      ++begin;
    } else {
      --end;
    }
  }
}

vector<vector<int>> threeSum(vector<int> vec) {
  vector<vector<int>> ret;
  if (vec.size() < 3)
    return ret;

  sort(vec.begin(), vec.end());
  for (int i = 0; i < vec.size() - 2;) {
    sumInSortedVec(vec, ret, i);
    int tmp = vec[i];
    while (i < vec.size() && vec[i] == tmp) {
      ++i;
    }
  }
  return ret;
}

int main() {
  vector<int> vec = {-1, 0, 1, 2, -1, -4};
  vector<vector<int>> ret = threeSum(vec);
  printVec("threeSum", ret);

  return 0;
}
